#pragma once

#include <iostream>
using namespace std;
#include <vector>
#include <time.h>
#include <random>
#include <chrono>


namespace ns_skiplist
{
    struct SkiplistNode {
        int _val;
        vector<SkiplistNode*> _nextV;
        SkiplistNode(int val, int level) : _val(val), _nextV(level, nullptr) {}
    };
    class Skiplist {
        typedef SkiplistNode Node;

    public:
        Skiplist() {
            srand(time(0));
            _head = new Node(-1, 1);
        }

        bool search(int target) {
            Node* cur = _head;
            int level = _head->_nextV.size() - 1;
            while (level >= 0) {
                if (cur->_nextV[level] != nullptr &&
                    cur->_nextV[level]->_val < target) {
                    cur = cur->_nextV[level];
                }
                else if (cur->_nextV[level] == nullptr ||
                    cur->_nextV[level]->_val > target) {
                    level--;
                }
                else {
                    return true;
                }
            }
            return false;
        }

        vector<Node*> findPrevNode(int num) {
            Node* cur = _head;
            int level = _head->_nextV.size() - 1;
            vector<Node*> prevV(level + 1, _head);
            while (level >= 0) {
                if (cur->_nextV[level] != nullptr &&
                    cur->_nextV[level]->_val < num) {
                    cur = cur->_nextV[level];
                }
                else if (cur->_nextV[level] == nullptr ||
                    cur->_nextV[level]->_val >= num) {
                    prevV[level] = cur;
                    level--;
                }
            }
            return prevV;
        }
        // size_t randomLevel() {
        //     size_t level = 1;
        //     // rand()->[0, RAND_MAX]
        //     while (rand() <= RAND_MAX * _p && level < _maxLevel) {
        //         ++level;
        //     }
        //     return level;
        // }
        size_t randomLevel() {
            static std::default_random_engine generator(
                std::chrono::system_clock::now().time_since_epoch().count());
            static std::uniform_real_distribution<double> distribution(0.0, 1.0);

            size_t level = 1;
            while (distribution(generator) <= _p && level < _maxLevel) {
                ++level;
            }
            return level;
        }
        void add(int num) {
            vector<Node*> prevV = findPrevNode(num);
            size_t n = randomLevel();
            Node* newnode = new Node(num, n);
            if (n > _head->_nextV.size()) {
                _head->_nextV.resize(n, nullptr);
                prevV.resize(n, _head);
            }
            for (size_t i = 0; i < n; i++) {
                newnode->_nextV[i] = prevV[i]->_nextV[i];
                prevV[i]->_nextV[i] = newnode;
            }
        }

        bool erase(int num) {
            vector<Node*> prevV = findPrevNode(num);
            if (prevV[0]->_nextV[0] == nullptr ||
                prevV[0]->_nextV[0]->_val != num) {
                return false;
            }
            else {
                Node* del = prevV[0]->_nextV[0];
                for (size_t i = 0; i < del->_nextV.size(); i++) {
                    prevV[i]->_nextV[i] = del->_nextV[i];
                }
                delete del;
                return true;
            }
        }

    private:
        Node* _head;
        size_t _maxLevel = 32;
        double _p = 0.5;
    };

    /**
     * Your Skiplist object will be instantiated and called as such:
     * Skiplist* obj = new Skiplist();
     * bool param_1 = obj->search(target);
     * obj->add(num);
     * bool param_3 = obj->erase(num);
     */
}
